#pragma once
#include "../strings/md5.h"
#include "LinkList.h"
#include "LinkedHashMap.h"

#ifndef BASSERT
#define BASSERT  // TODO
#endif

#ifndef BLOGINFO
#define BLOGINFO
#endif

#ifndef WIN32
#include <sys/mman.h>
#else
#include <windows.h>
#endif

namespace qb {
namespace base {
typedef unsigned int uint;
typedef unsigned char uchar;

namespace util {
bool S_CORE_EXPORT GetUpperExp2(int& num, unsigned short& bitcount);
void ShiftMemory(uchar* mem, int bytes, int step) {
  // step为正表示向后移动,为负表示向左移动
  if (bytes > 0 && step != 0) memmove(mem + step, mem, bytes);
}
unsigned int InlineTime33Hash(const char* str, int len) {
  unsigned int hash = 5381;
  const char* pend = str + len;
  while (str < pend) {
    hash += (hash << 5) + (*str++);
  }
  return (hash & 0x7FFFFFFF);
}
}  // namespace util

template <typename EntryType, typename KeyType, typename ValueType, int N = 256,
          bool MULTI = false>
class DEL_ALIGN FStringChunk {
  enum {
    SSEBit = 4,
    SSESize = 1 << SSEBit,  // 表示一次SSE搜索的项目个数

#ifdef WIN32
#ifdef _WIN64
    StartPos =
        N -
        24,  // 表示起始偏移量,也是最大,每次增加,偏移量会递减
#else
    StartPos =
        N -
        16,  // 表示起始偏移量,也是最大,每次增加,偏移量会递减
#endif
#else
    StartPos =
        N -
        24,  // 表示起始偏移量,也是最大,每次增加,偏移量会递减
#endif
             //  10 是末尾占据重要元信息的m_count,m_pos,m_mask,m_next等四个字段
  };

  typedef LinkedHashMapStat Stat;
  class EntryTypeDefault {  // 表示模板参数EntryType应该实现的接口
   public:
    uint GetHash() const;  // 计算当前键的哈希值
    int Bytes() const;  // 计算当前键值总共占据的内存,包括字符串末尾的0
    ValueType GetValue();  // 获取当前值,已经编码到结构体中
    void SetValue(
        const ValueType& v);  // 设置当前值,将值编码到结构体中,不会额外增加内存
    void CopyTo(const ValueType& value, char* buf,
                int bytes);  // 将当前键和值value,写入到内存buf中
  };

 public:
  typedef FStringChunk Chunk;
  typedef std::pair<const FStringChunk*, int> ChunkIndex;
  using HashPair = std::pair<std::size_t, uint8_t>;

 private:
  /*
  m_buffer的内存布局:
  uchar	m_tags[m_count];	// 标签
  uchar	m_pos[m_count];		// 偏移量

  ......
  EntryType  第m_count-1个entry
  EntryType  第m_count-2个entry
  ......
  EntryType  第1个entry
  EntryType  第0个entry
  */

  uchar m_count;  // 当前Chunk放入的字符串个数
  uchar m_pos;  // 最后一个放入的字符串位置,即在m_buffer中的偏移量,也是索引
  ushort m_pad1;
  uint m_pad2;  //
  uint m_mask;  // 使用这个而不是搜索时计算,有明显的性能提升
  union {
    Chunk* m_next;    // 下一个指针
    size_t m_offset;  // 下一个Chunk在文件中的偏移量
  };
  uchar m_buffer[StartPos];  // 内存布局:m_count
 public:
  FStringChunk(FStringChunk* next) : m_next(next), m_count(0), m_pos(StartPos) {
    SetCount(0);
    static_assert(sizeof(FStringChunk) == N,
                  "sizeof(FStringChunk) != N failed");
  }
  void SetCount(uchar count) {
    m_count = count;
    m_mask = static_cast<unsigned>(~(~uint64_t{0} << m_count));
  }
  void Clear() {
    // MEMSET(m_buffer, 0, N);
    m_next = nullptr;
    m_pos = StartPos;
    SetCount(0);
  }
  FStringChunk* GetNext() { return m_next; }
  const FStringChunk* GetNext() const { return m_next; }
  void SetNext(FStringChunk* next) { m_next = next; }
  void SetNextOffset(size_t offset) { m_offset = offset; }
  size_t GetOffset() const { return m_offset; }
  bool Get(const KeyType& key, const HashPair& hp, ValueType& value) const {
    int index = find(key, hp);
    if (index >= 0) {
      value = itemAddr(index)->GetValue();
      return true;
    }
    return false;
  }
  bool Erase(const KeyType& key, const HashPair& hp) {
    int index = find(key, hp);
    if (index >= 0) {
      return EraseImpl(index);
    }
    return false;
  }
  bool EraseImpl(int index) {
    // 将该Chunk的指定索引的键值对删除,并同时恢复tags和偏移量数组
    if (index >= m_count || index < 0) return false;
    // Check();
    // FStringChunk* chunk = Clone();
    // again:
    uchar* tags = m_buffer;
    uchar* pos = m_buffer + m_count;
    // 将最前面的内容往后移动,使得index对应的内容被覆盖掉
    uchar delpos = pos[index];   // 旧的要删除的位置
    int bytes = delpos - m_pos;  // 要移动的内存大小
    EntryType* et = itemAddr(index);
    int gap =
        EntryType::CalcBytes(et->GetKey(), et->GetValue());  // 要消除的空间
    util::ShiftMemory(m_buffer + m_pos, bytes, gap);

    // 将tags数组往左移动1个字节
    util::ShiftMemory(tags + index + 1, m_count - 1 - index, -1);

    // 修正pos数组
    //  将偏移量左侧部分往左移动1个字节,右侧部分往左移动2个字节,且对应的值都增加gap
    for (int i = 0; i < index; i++) {
      pos[i - 1] = pos[i] < delpos ? (pos[i] + gap) : (pos[i]);
    }
    for (int i = index + 1; i < m_count; i++) {
      pos[i - 2] = pos[i] < delpos ? (pos[i] + gap) : (pos[i]);
    }
    m_pos += gap;
    SetCount(m_count - 1);
    // if (!Check())
    //{
    // Restore(chunk);
    // goto again;
    //}
    // if (chunk)delete chunk;
    return true;
  }
  static HashPair splitHash(std::size_t hash) {
    uint8_t tag =
        (hash & 0x000000ff);  // | 0x80;	//
                              // 使用低7个bit用于tag,第8个保留用于识别是否为空
    return std::make_pair(hash, tag);
  }
  FStringChunk* Clone() {
    FStringChunk* chunk = new FStringChunk(nullptr);
    memcpy(chunk, this, sizeof(FStringChunk));
    return chunk;
  }
  void Restore(FStringChunk* chunk) {
    memcpy(this, chunk, sizeof(FStringChunk));
  }
  bool Check() {
    BASSERT(m_pos <= StartPos);
    uchar* tags = m_buffer;
    uchar* pos = m_buffer + m_count;
    int nerror = 0;
    for (int i = 0; i < m_count; i++) {
      EntryType* et = itemAddr(i);
      KeyType kt = et->GetKey();
      std::size_t hash = kt.GetHash();
      if (splitHash(hash).second != tags[i]) nerror++;
    }
    return nerror <= 0;
  }
  int Count() const { return m_count; }
  bool IsEmpty() const { return m_count <= 0; }
  bool Exist(const KeyType& key, const HashPair& hp) const {
    int index = find(key, hp);
    return index >= 0;
  }
  void PutAt(int index, const ValueType& value) {
    // 上层确定已经找到过,这里不做检查
    itemAddr(index)->SetValue(value);
  }
  bool PutDirectly(const KeyType& key, const HashPair& hp,
                   const ValueType& value) {
    // 为什么需要update:新建Chunk不需要重新搜索
    // 如果已经上层已经确定搜索过了,这里也不需要重新搜索
    // 外界已经探测到,key可以放进去了
    // Check();
    int bytes = EntryType::CalcBytes(key, value);
    uchar* tags = m_buffer;
    uchar* pos = m_buffer + m_count;
    uchar newpos = m_pos - bytes;
    // 将偏移量数组向后移动1个字节
    util::ShiftMemory(pos, m_count, 1);
    // 改写最后一个标签和偏移量,别将键值写入到指定位置
    tags[m_count] = hp.second;
    pos[m_count + 1] = newpos;
    EntryType* pentry = (EntryType*)(m_buffer + newpos);
    pentry->Build(key, value, bytes);
    m_pos -= bytes;
    SetCount(m_count + 1);

    // const EntryType* et = itemAddr(m_count - 1);
    // BASSERT(et && et->EqualKey(key));
    // Check();
    return true;
  }

  bool PutWithSpace(const KeyType& key, const HashPair& hp,
                    const ValueType& value) {
    // 为什么需要update:新建Chunk不需要重新搜索
    // 如果已经上层已经确定搜索过了,这里也不需要重新搜索
    if (m_count >= SSESize)  // 最多放16个
      return false;
    int bytes = EntryType::CalcBytes(key, value);
    int leftSpace = space();
    if (bytes + 2 <= leftSpace) {
      return PutDirectly(key, hp, value);
    }
    // 放不下去,交给外部处理
    return false;
  }

  bool PutWithSearch(const KeyType& key, const HashPair& hp,
                     const ValueType& value, bool update) {
    // 为什么需要update:新建Chunk不需要重新搜索
    // 如果已经上层已经确定搜索过了,这里也不需要重新搜索
    if (update) {
      int index = find(key, hp);
      if (index >= 0) {
        itemAddr(index)->SetValue(value);
        return true;
      }
    }
    return PutWithSpace(key, hp, value);
  }
  void GetStat(Stat& st) {
    st.cache++;
    st.bytes += sizeof(FStringChunk) - space();
    st.count += m_count;

    int level = 1;
    auto next = m_next;
    while (next) {
      level++;
      next = next->GetNext();
    }
    if (st.max_level < level) st.max_level = level;
    st.sum_level += level;

    if (m_next) m_next->GetStat(st);
  }

  const EntryType* itemAddr(int index) const {
    // 最开头m_count个uchar是tag数组
    // 然后m_count是偏移量数组
    // index>=0 && index<m_count
    const uchar* posArray = m_buffer + m_count;
    uchar pos = posArray[index];
    return (const EntryType*)(m_buffer + pos);
  }
  EntryType* itemAddr(int index) {
    const uchar* posArray = m_buffer + m_count;
    uchar pos = posArray[index];
    return (EntryType*)(m_buffer + pos);
  }

 protected:
  TagVector const* tagVector(int nloop) const {
    return static_cast<TagVector const*>(
        static_cast<void const*>(&m_buffer[nloop << SSEBit]));
  }
  SparseMaskIter tagMatchIter(std::size_t needle, int nloop,
                              unsigned int fullMask) const {
    FOLLY_SAFE_DCHECK((needle & 0x80) != 0, "");
    // unsigned int fullMask = m_mask;// static_cast<unsigned>(~(~uint64_t{ 0 }
    // << count)); kFullMask = static_cast<unsigned>(~(~uint64_t{ 0 } <<
    // kCapacity))
    auto tagV = _mm_load_si128(tagVector(nloop));
    auto needleV = _mm_set1_epi8(static_cast<uint8_t>(needle));
    auto eqV = _mm_cmpeq_epi8(tagV, needleV);
    auto mask = _mm_movemask_epi8(eqV) & static_cast<unsigned>(fullMask);
    return SparseMaskIter{mask};
  }

  int space() const {
    // m_pos是上一次追加的位置,每次追加,m_pos都递减
    // 开头要占据两个长度为m_count的数组,分别是tags数组和偏移量数组
    // 中间的就是剩余空间
    return m_pos - m_count * sizeof(uchar) * 2;
  }

 public:
  template <bool MULTI2>
  int findimpl(KeyType const& key, const HashPair& hp) const {
    if (!MULTI2) {
      // 如果计数超过16,则进行惰轮sse搜索,nloop表示当前轮次,nbase表示当前轮的基数索引
      // 在当前FStringChunk中查找对应的键值
      // prefetchAddr(m_buffer);
      // 经过测试,比MULTI为true时性能略高

      // unsigned int fullMask = m_mask;// static_cast<unsigned>(~(~uint64_t{ 0
      // } << count)); TagVector const* tagPtr = static_cast<TagVector
      // const*>(static_cast<void const*>(m_buffer)); prefetchAddr((const
      // char*)this + (N >> 1)); std::size_t needle = hp.second; auto tagV =
      // _mm_load_si128(tagPtr); auto needleV =
      // _mm_set1_epi8(static_cast<uint8_t>(needle)); auto eqV =
      // _mm_cmpeq_epi8(tagV, needleV); auto mask = _mm_movemask_epi8(eqV) &
      // static_cast<unsigned>(fullMask); SparseMaskIter hits(mask);

      prefetchAddr((const char*)this + (N >> 1));
      auto hits = tagMatchIter(hp.second, 0, m_mask);
      while (hits.hasNext()) {
        auto i = hits.next();
        const EntryType* et = itemAddr(i);
        if (et->EqualKey(key)) return i;
      }
      return -1;
    }
    // 如果计数超过16,则进行惰轮sse搜索,nloop表示当前轮次,nbase表示当前轮的基数索引
    // 在当前FStringChunk中查找对应的键值
    // 支持在256字节中存储多轮查询,16个为一轮,性能测试表明16个就足够,多了反而降低
    int nloop = 0, nbase = 0, mcount = m_count;
    while (nbase < mcount) {
      int count = (nbase + SSESize) <= mcount ? SSESize : (mcount - nbase);
      // prefetchAddr(m_buffer);
      unsigned int fullMask = static_cast<unsigned>(~(~uint64_t{0} << count));
      auto hits = tagMatchIter(hp.second, nloop, fullMask);
      while (hits.hasNext()) {
        auto i = hits.next();
        if (itemAddr(i + nbase)->EqualKey(key)) return nbase + i;
      }
      nloop++;
      nbase += SSESize;
    }
    return -1;
  }

  int find(KeyType const& key, const HashPair& hp) const {
    // 如果计数超过16,则进行惰轮sse搜索,nloop表示当前轮次,nbase表示当前轮的基数索引
    // 在当前fstringchunk中查找对应的键值
    bool sse2 = sse::supports_sse2();
    return sse2 ? findimpl<MULTI>(key, hp) : findWithoutSSE(key);
  }
  int findWithoutSSE(KeyType const& key) const {
    for (int i = 0; i < m_count; i++) {
      if (itemAddr(i)->EqualKey(key)) return i;
    }
    return -1;
  }
};
// static_assert(sizeof(FStringChunk) == 256, "");

struct S_CORE_EXPORT StringView {  // 用于轻量级传递参数
  int len;
  const char* str;
  StringView() : len(0), str(nullptr) {}
  StringView(const StringView& view) : len(view.len), str(view.str) {}
  StringView(const char* s) : str(s), len(s ? strlen(s) : 0) {}
  StringView(const char* s, int l) : str(s), len(l) {}
  StringView& operator=(const StringView& view) {
    len = view.len;
    str = view.str;
    return *this;
  }
  bool operator==(const StringView& view) const {
    return len == view.len && memcmp(str, view.str, len) == 0;
  }
  bool operator!=(const StringView& view) const {
    return !(len == view.len && memcmp(str, view.str, len) == 0);
  }
  uint GetHash() const  // 计算当前键的哈希值
  {
    return util::InlineTime33Hash(str, len);
  }
  int Bytes() const  // 计算当前键值总共占据的内存,包括字符串末尾的0
  {
    return sizeof(uint) + len + 1;
  }
};
struct S_CORE_EXPORT StringIntEntry {  // 用于紧凑式存储内容
  uint len : 8;                        // 最大长度为256
  uint id : 24;                        // 最大支持2^24即1600w的数字
  char str[4];  // 注意,str实际内容长度一般超过这个数组
 public:
  StringIntEntry() : len(0), id(0) { str[0] = '\0'; }
  uint GetValue() const  // 获取当前值,已经编码到结构体中
  {
    return id;
  }
  StringView GetKey() const { return StringView(str, len); }
  void SetValue(
      const uint& v)  // 设置当前值,将值编码到结构体中,不会额外增加内存
  {
    id = v;
  }
  void Build(const StringView& key, const uint& value,
             int bytes)  // 将当前键和值value,写入到内存buf中
  {
    // BASSERT(key.Bytes() == bytes);
    len = key.len;
    id = value;
    memcpy(str, key.str, len);
    str[len] = '\0';
  }
  static int CalcBytes(const StringView& key, const uint& value) {
    return key.Bytes();
  }
  bool EqualKey(const StringView& view) const {
    // if (len != view.len)return false;
    // const char* p1 = view.str;
    // const char* p2 = str;
    // const char* end = str + len;
    // while (p2 < end && *p1++ == *p2++){}
    // return true;
    // return len == view.len && 0==A_memcmp(view.str, str, len);
    return len == view.len && 0 == memcmp(view.str, str, len);
    // return len == view.len && strncmp(view.str, str, len) == 0;
    // return len == view.len && EqualMemoryComp(view.str, str, len);
  }
};

struct S_CORE_EXPORT StringIntPair {  // 用于紧凑式存储内容
  uint id;                            // 最大支持2^24即1600w的数字
  char str[4];  // 注意,str实际内容长度一般超过这个数组
 public:
  StringIntPair() : id(0) { str[0] = '\0'; }
  uint GetValue() const  // 获取当前值,已经编码到结构体中
  {
    return id;
  }
  StringView GetKey() const { return StringView(str, strlen(str)); }
  void SetValue(
      const uint& v)  // 设置当前值,将值编码到结构体中,不会额外增加内存
  {
    id = v;
  }
  void Build(const StringView& key, const uint& value,
             int bytes)  // 将当前键和值value,写入到内存buf中
  {
    // BASSERT(key.Bytes() == bytes);
    id = value;
    memcpy(str, key.str, key.len);
    str[key.len] = '\0';
  }
  bool EqualKey(const StringView& view) const {
    // 经过测试strcmp比strncmp速度还快
    // return len == view.len && 0==A_MEMCMP(view.str, str, len);
    return strcmp(str, view.str) == 0;
    // return memcmp(view.str, str, len);
    // return len == view.len && strncmp(view.str, str, len) == 0;
    // return len == view.len && EqualMemoryComp(view.str, str, len);
  }
};

template <int N>
class PagedPool {
  enum { Magic = 0xfed0cfad, PageSize = 64 * 1024, EmptyMask = 0xffffffff };
  struct ItemInfo {
    char data[N];
  };
  class PageHead {
    PageHead* next;  // 单链表
    PageHead* prev;
    uint magic;      // 常量值,用于检测问题
    uint bytes;      // 整体Page的尺寸内存,通常是64kb
    int size;        // 每个的大小
    int count;       // 实际放入的个数
    int capcity;     // 实际可容纳的个数
    int nbitmap;     // bitmap数组的长度
    int offset;      // 第一个item的偏移量,在bitmap数组之后
    uint bitmap[1];  // 实际长度由nbitmap指定,每一个bit为1表示对应位置是否被占用
   public:
    PageHead()
        : next(nullptr),
          prev(nullptr),
          magic(Magic),
          bytes(PageSize),
          size(N),
          count(0) {
      for (int i = 1; i < 16; i++) {
        offset = i * size;
        capcity = (bytes - offset) / size;
        nbitmap = capcity / 32;
        if (capcity % 32 != 0) nbitmap++;

        if (sizeof(PageHead) + (nbitmap - 1) * sizeof(uint) < (size_t)size)
          break;
      }
      for (int i = 0; i < nbitmap; i++) bitmap[i] = EmptyMask;
    }
    PageHead* GetNext() const { return next; }
    PageHead* GetPrev() const { return prev; }
    void SetNext(PageHead* n) { next = n; }
    void SetPrev(PageHead* p) { prev = p; }

    bool Check() const {
      return magic == Magic && bytes == PageSize && size == N;
    }
    bool IsFull() const { return count >= capcity; }
    bool IsEmpty() const { return count <= 0; }
    void* Alloc() {
      if (count >= capcity) return nullptr;
      int index = FirstEmpty();
      if (index < 0 || index >= capcity) return nullptr;
      void* ptr = At(index);
      Set(index, true);
      count++;
      return ptr;
    }
    bool Free(void* ptr, int len) {
      const char* base = (const char*)this;
      if (ptr < base || ptr >= base + bytes || size != len) return false;
      int index = (((const char*)ptr - base) - offset) / size;
      if (ptr == At(index)) {
        Set(index, false);
        count--;
        return true;
      }
      return false;
    }

   protected:
    void* At(int index) {
      const char* base = (const char*)this;
      return (void*)(base + offset + index * size);
    }
    void Set(int index, bool used) {
      int pos = index / 32;
      int bit = index - pos * 32;
      uint flag = ((uint)1) << bit;
      if (used)
        bitmap[pos] &= ~flag;  // 设置0
      else
        bitmap[pos] |= flag;  // 设置1
    }
    int FirstEmpty() const {
      for (int i = 0; i < nbitmap; i++) {
        FirstEmptyInMask mask(bitmap[i]);
        if (mask.hasIndex()) {
          return mask.index() + i * 32;
        }
      }
      return -1;
    }
  };
  DoubleLinkList<PageHead> m_slist;  // 有空位的
  DoubleLinkList<PageHead> m_full;   // 已经满了的
 public:
  PagedPool() {}
  ~PagedPool() {
    FreePage(m_slist.GetHead());
    FreePage(m_full.GetHead());
  }
  void Swap(PagedPool& other) {
    m_slist.Swap(other.m_slist);
    m_full.Swap(other.m_full);
  }
  void* Alloc() {
    PageHead* head = m_slist.GetHead();
    if (!head) {
      m_slist.InsertHead(NewPage());
      head = m_slist.GetHead();
    }

    // BASSERT(!head->IsFull());
    void* ptr = head->Alloc();
    if (head->IsFull()) {
      m_full.Append(m_slist.PickHead());
    }
    return ptr;
  }
  void Free(void* ptr, int size) {
    // PageHead都是以PageSize对齐
    uintptr_t addr = (uintptr_t)(ptr);
    addr = (addr / PageSize) * PageSize;
    PageHead* page = (PageHead*)addr;

    if (page) {
      BASSERT(page->Check());
      bool s1 = m_slist.Contain(page);
      bool f1 = m_full.Contain(page);
      BASSERT(s1 || f1);
      bool full = page->IsFull();
      bool suc = page->Free(ptr, size);
      if (suc) {
        if (full) {
          // 将page从m_full中迁移到m_slist中
          m_full.Remove(page);
          m_slist.Append(page);
        } else if (page->IsEmpty()) {
          m_slist.Remove(page);
          FreePage(page);
        }
      } else {
        BLOGINFO("[CACHE]page Free item failed");
      }
    } else {
      BLOGINFO("[CACHE]invalid PageHead:0x%08x", page);
    }
  }
  int GetBytes() const {
    return (m_slist.GetCount() + m_full.GetCount()) * PageSize + sizeof(*this);
  }

 protected:
  PageHead* NewPage() {
#ifdef WIN32
    void* ptr =
        VirtualAlloc(NULL, PageSize, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
    // TODO: address is 0?!
    void* ptr = malloc(PageSize);
#endif
    return new (ptr) PageHead();
  }
  void FreePage(PageHead* page) {
    while (page) {
      PageHead* temp = page;
      page = page->GetNext();
#ifdef WIN32
      VirtualFree(temp, 0, MEM_RELEASE);
#else
      free(temp);
#endif
    }
  }
};

class HashmapHint {
  int m_capcity, m_keylen;

 public:
  HashmapHint(int capcity, int keylen) : m_capcity(capcity), m_keylen(keylen) {}
  ~HashmapHint() {}
  int Capcity() const { return m_capcity; }
  int KeyLength() const { return m_keylen; }
};
template <typename EntryType, typename KeyType, typename ValueType,
          typename CacheLine =
              FStringChunk<EntryType, KeyType, ValueType, 256> >
class StringIntHashMap {
 public:
  enum {
    Magic = 0xABFE,
    kCacheSize = 64,    // 一级缓存行大小通用值为64字节
    kBitCountMin = 6,   //
    kBitCountMax = 24,  // 限制哈希插槽最大值为1<<24,即16777216
    // kKeyCount = (kCacheSize - sizeof(void*)) / sizeof(EntryType),
    // 一个缓存行CacheLine中放置几个值项
  };
  enum {
    kFlagUsePool = 0x0001,  // 是否开启虚拟内存池分配器
                            // 使用后,构建时间和销毁时间略有缩短,幅度不大
    kFlagUseExpand = 0x0002,     // 是否允许自动扩展
    kFlagListForBlank = 0x0004,  // 是否允许整个单链表查找空位
                                 // 开启后减少内存,但是构建速度会慢
  };
  typedef LinkedHashMapStat Stat;

 protected:
  typedef CacheLine* SlotPtr;
  typedef std::vector<SlotPtr> SlotArray;
  typedef typename CacheLine::ChunkIndex ChunkIndex;
  struct FileHead {    // 文件头部
    uint magic;        //
    uint hashoffset;   //
    uint hashlength;   //
    uint chunkoffset;  //
    uint chunksize;    //
    uint chunkcount;   //
    uint keycount;     //
  };
  // 使用PagedPool的好处:内存碎片少,销毁时间非常短,性能上并没有额外的优势
  typedef PagedPool<sizeof(CacheLine)> CachePool;

 protected:
  SlotArray m_slots;  // m_slot_count个,12个字节
  CachePool m_pool;   // 虚拟内存池分配器,24个字节
  ushort
      m_flag;  // 功能标志位,后续可以考虑用模板policy实现,性能更好,见folly的F14Table
  ushort m_bitcount;  // 如果插槽长度刚好是2的n次幂,那么m_bitcount==n,否则为0
  int m_count;      // 真实放入的键值对个数
  int m_nodecount;  // CacheLine的总个数
  int m_bitmask;    // (((uint)1)<<m_bitcount)-1,用来计算哈希位置
 public:
  StringIntHashMap(int slotcapcity = 1024, bool usePool = true,
                   bool useExpand = true)
      : m_count(0), m_nodecount(0), m_bitcount(0), m_bitmask(0), m_flag(0) {
    // m_flag |= kFlagListForBlank;
    if (usePool) m_flag |= kFlagUsePool;
    // if (useExpand)m_flag |= kFlagUseExpand;

    // debug下vector大小是16,
    // static_assert(sizeof(SlotArray) == 16,"vector");
    // static_assert(sizeof(*this) == 40 + 16,"StringIntHashMap");
    // 经过测试,对于20w的数据1w个插槽是合适的,效率和内存综合最佳
    // NameDict插入时间性能有待优化, 改成哈希表可能更好
    //	CacheLine是整块的内存, 可以预先提前分配
    //	bkey可以使用编码进一步减少尺寸
    //	参考F14Map, 使用并行搜索, 增大CacheLine尺寸会导致空间浪费
    // F14Map并行搜索 : 为每个节点生成一个1个字节的哈希值,
    // 将16个节点的哈希值凑成一个128位值, 然后使用intel sse指令 			 一次性搜索16个

    // 确保哈希长度为2的m_bitcount次幂,这样计算位置速度最快
    if (util::GetUpperExp2(slotcapcity, m_bitcount))
      m_bitmask = (1 << m_bitcount) - 1;
    m_slots.reserve(slotcapcity);
    for (int i = 0; i < slotcapcity; i++) m_slots.emplace_back(nullptr);
  }
  ~StringIntHashMap() { Clear(); }
  int GetCount() const { return m_count; }
  int GetLength() const { return m_slots.capacity(); }
  int GetSlotCount() const { return m_slots.size(); }
  double GetLoadRatio() const {
    return m_count * 1.0 / (m_nodecount * CacheLine::kKeyCount);
  }
  using HashPair = std::pair<std::size_t, uint8_t>;
  using size_type = size_t;

 protected:  // 迭代器
  int CalcCount() const {
    int ncount = 0;
    for (int i = 0; i < (int)m_slots.size(); i++) {
      const CacheLine* cache = m_slots[i];
      while (cache) {
        ncount += cache->Count();
        cache = cache->GetNext();
      }
    }
    return ncount;
  }
  ChunkIndex Next(int& slot, const ChunkIndex& it) const {
    const CacheLine* cache = it.first;
    // BASSERT(cache);
    if (it.second + 1 < cache->Count()) return ChunkIndex{cache, it.second + 1};
    cache = cache->GetNext();
    if (cache && cache->Count() > 0) return ChunkIndex{cache, 0};
    while (slot + 1 < (int)m_slots.size()) {
      slot++;
      cache = m_slots[slot];
      if (cache) {
        return ChunkIndex{cache, 0};
      }
    }
    // 模拟end()
    slot = 0;
    return ChunkIndex{nullptr, -1};
  }

 public:  // std::map的类似接口
  class iterator {
    const StringIntHashMap* m_owner;  // 拥有者
    int m_slot;                       // 一个个插槽来遍历
    ChunkIndex m_itor;                // 该插槽上的单链表位置
   public:
    iterator(const StringIntHashMap* owner)
        : m_owner(owner), m_slot(0), m_itor(nullptr, -1) {}
    iterator(const StringIntHashMap* owner, int slot, const ChunkIndex& ci)
        : m_owner(owner), m_slot(slot), m_itor(ci) {}
    iterator(const iterator& it)
        : m_owner(it.m_owner), m_slot(it.m_slot), m_itor(it.m_itor) {}
    iterator(iterator&& it) : m_owner(nullptr), m_slot(0), m_itor(nullptr, -1) {
      std::swap(m_owner, it.m_owner);
      std::swap(m_slot, it.m_slot);
      std::swap(m_itor, it.m_itor);
    }
    iterator operator=(iterator&& it) {
      std::swap(m_owner, it.m_owner);
      std::swap(m_slot, it.m_slot);
      std::swap(m_itor, it.m_itor);
      return *this;
    }
    iterator& operator=(const iterator& it) {
      m_owner = it.m_owner;
      m_slot = it.m_slot;
      m_itor = it.m_itor;
      return *this;
    }
    bool operator!=(const iterator& it) const {
      return m_owner != it.m_owner || m_slot != it.m_slot ||
             m_itor != it.m_itor;
    }
    bool operator==(const iterator& it) const {
      return m_owner == it.m_owner && m_slot == it.m_slot &&
             m_itor == it.m_itor;
    }
    iterator operator++() {  // 前置:更改自身,再返回
      if (m_owner) {
        m_itor = m_owner->Next(m_slot, m_itor);
      }
      return *this;
    }
    KeyType first() const {  // 可能会抛出异常,因为迭代器可能失效
      return m_itor.first->itemAddr(m_itor.second)->GetKey();
    }
    ValueType second() const {  // 可能会抛出异常,因为迭代器可能失效
      return m_itor.first->itemAddr(m_itor.second)->GetValue();
    }
  };
  size_t size() const { return m_count; }
  iterator begin() const {
    for (int i = 0; i < (int)m_slots.size(); i++) {
      const CacheLine* cache = m_slots[i];
      while (cache) {
        if (!cache->IsEmpty()) {
          return iterator(this, i, ChunkIndex{cache, 0});
        }
      }
    }
    return iterator(this);
  }
  iterator end() const { return iterator(this); }
  iterator find(const KeyType& key) const {
    auto hp = splitHash(key.GetHash());
    auto it = Find(key, hp);
    return iterator(this, 0, it);
  }
  size_type erase(const KeyType& key) { return Erase(key) ? 1 : 0; }

 public:
  bool Get(const KeyType& key, ValueType& value) {
    auto hp = splitHash(key.GetHash());
    auto it = Find(key, hp);
    if (it.first) {
      value = it.first->itemAddr(it.second)->GetValue();
      return true;
    }
    return false;
  }
  void GetValues(std::vector<ValueType>& values) {
    values.clear();
    values.reserve(GetCount());
    for (int i = 0; i < (int)m_slots.size(); i++) {
      const CacheLine* cache = m_slots[i];
      while (cache) {
        for (int k = 0; k < cache->Count(); k++) {
          const EntryType* et = cache->itemAddr(k);
          values.push_back(et->GetValue());
        }
        cache = cache->GetNext();
      }
    }
  }
  int PutAtSlot(const KeyType& key, const HashPair& hp,
                const ValueType& value) {
    // 将键值写入到hp计算到的插槽中,成功返回插槽编号,否则返回-1
    int slot = GetPos(hp);
    SlotPtr cache = m_slots[slot];
    if (cache && cache->PutWithSpace(key, hp, value)) {
      m_count++;
      return slot;
    }
    return -1;
    // 开启kFlagListForBlank后的代码;
    // 鉴于kFlagListForBlank对内存影响很小,不放开使用
    // while (cache)
    //{
    //	if (cache->Put(key, hp, value, false))
    //	{
    //		m_count++;
    //		return slot;
    //	}
    //	cache = (kFlagListForBlank&m_flag)?cache->GetNext():nullptr;
    // }
    // return -1;
  }
  void Put(const KeyType& key, const ValueType& value) {
    auto hp = splitHash(key.GetHash());
    auto it = Find(key, hp);
    if (it.first) {
      // 找到了必定能写入成功,因为value是固定尺寸大小
      (const_cast<CacheLine*>(it.first))->PutAt(it.second, value);
      return;
    }

    // 第一个不能写入,后续的即使有空间,为了性能考虑也不做尝试
    int slot = GetPos(hp);
    SlotPtr cache = m_slots[slot];
    if (cache && cache->PutWithSpace(key, hp, value)) {
      m_count++;
      return;
    }
    if ((m_flag & kFlagUseExpand) &&
        (size_t)m_nodecount >= (m_slots.size() << 1)) {
      ushort bitcount = 0;
      int capcity = m_slots.size() + 1;
      util::GetUpperExp2(capcity, bitcount);
      if (ExpandSlots(capcity, m_flag & kFlagUsePool)) {
        slot = GetPos(hp);
        cache = m_slots[slot];
        if (cache && cache->PutWithSpace(key, hp, value)) {
          m_count++;
          return;
        }
      }
    }
    cache = NewCache(m_slots[slot]);
    m_slots[slot] = cache;
    cache->PutDirectly(key, hp, value);
    m_nodecount++;
    m_count++;
  }
  bool Erase(const KeyType& key) {
    bool suc = false;
    SlotPtr prev = nullptr;
    auto hp = splitHash(key.GetHash());
    int slot = GetPos(hp);
    SlotPtr cache = m_slots[slot];
    while (cache) {
      suc = cache->Erase(key, hp);
      if (suc) {
        if (cache->IsEmpty()) {
          if (prev == nullptr)
            m_slots[slot] = cache->GetNext();
          else
            prev->SetNext(cache->GetNext());
          DelCache(cache);
          m_nodecount--;
        }
        break;
      }
      prev = cache;
      cache = cache->GetNext();
    }
    if (suc) m_count--;
    return suc;
  }
  bool Exist(const KeyType& key) const {
    auto it = Find(key, splitHash(key.GetHash()));
    return it.first != nullptr;
  }
  void Expand(int keycapcity, double keyBytes = 0.0, bool usePool = true) {
    // keycapcity是要放置的key大概总共有多少个
    // 首先预估一下每个键值的平均长度
    // 这里需要计算一下最佳插槽个数
    if (keyBytes <= 1.0) {
      keyBytes = PredictKeyLenth();
      BLOGINFO("[CACHE]calc keylen=%.2f", keyBytes);
    }
    int capcity = CalcSlotLength(keycapcity, keyBytes, 0.9);
    if (capcity <= (int)m_slots.capacity()) return;
    ExpandSlots(capcity, usePool);
  }
  void Swap(StringIntHashMap& temp) {
    std::swap(m_slots, temp.m_slots);
    m_pool.Swap(temp.m_pool);
    std::swap(m_flag, temp.m_flag);
    std::swap(m_bitcount, temp.m_bitcount);

    std::swap(m_count, temp.m_count);
    std::swap(m_nodecount, temp.m_nodecount);
    std::swap(m_bitmask, temp.m_bitmask);
  }

  bool Load(const char* buf, int fsize) {
    // 从磁盘文件中重新加载此数据
    if (buf == nullptr || fsize < sizeof(FileHead)) return false;
    const FileHead* head = (const FileHead*)buf;
    if (head->magic != Magic) return false;
    if (fsize != head->chunkoffset + head->chunksize * head->chunkcount)
      return false;
    if (sizeof(CacheLine) != head->chunksize) return false;
    int md5size = sizeof(MD5::tMD5);
    int offset = sizeof(uint) + md5size;
    uint* slots = (uint*)(buf + head->hashoffset);
    // MD5::tMD5 md5Check;
    // MD5::FromString((const char*)slots, head->hashlength*sizeof(uint),
    // md5Check, md5size); if (strcmp(md5Check, head->md5) != 0) 	return false;

    StringIntHashMap temp(head->hashlength);

    CacheLine* caches = (CacheLine*)(buf + head->chunkoffset);
    for (int i = 0; i < (int)head->hashlength; i++) {
      if (slots[i] == 0) continue;
      const CacheLine* cache = (const CacheLine*)(buf + slots[i]);
      CacheLine* prev = nullptr;
      while (cache) {
        // 处理内存中的
        CacheLine* cur = temp.NewCache(nullptr);
        if (prev == nullptr)
          temp.GetSlotHead(i) = cur;
        else
          prev->SetNext(cur);
        prev = cur;
        memcpy(cur, cache, sizeof(CacheLine));
        cur->SetNext(nullptr);

        // 处理从文件中加载的
        if (cache->GetOffset() == 0) break;
        cache = (const CacheLine*)(buf + cache->GetOffset());
      }
    }
    temp.m_count = head->keycount;
    temp.m_nodecount = head->chunkcount;
    Swap(temp);
    return true;
  }
  int Save(char* buf, int capcity) const {
    class PagedFileWriter {
      char* m_buf;
      int m_capcity;
      int m_filepos;
      int m_used;
      void* m_file;

     public:
      void Append(const char* buf, int size) {}
      void Write(int pos, const char* buf, int size) {
        // 从位置pos开始,写入内存buf,如果buf为0,那么写入内容0
      }
    };
    class MemoryWriter {
      char* m_buf;
      int m_capcity;
      int m_filepos;

     public:
      MemoryWriter(char* buf, int capcity)
          : m_buf(buf), m_capcity(capcity), m_filepos(0) {}
      void Append(const char* buf, int size) {
        if (buf)
          memcpy(m_buf + m_filepos, buf, size);
        else
          memset(m_buf + m_filepos, 0, size);
        m_filepos += size;
      }
      void Write(int pos, const char* buf, int size) {
        // 从位置pos开始,写入内存buf,如果buf为0,那么写入内容0
        memcpy(m_buf + pos, buf, size);
      }
    };
    MemoryWriter fwriter(buf, capcity);
    int nfsize = CalcFileSize();
    if (buf == nullptr) return nfsize;
    if (capcity < nfsize) return -1;

    const int ncachesize = sizeof(CacheLine);
    int headsize = sizeof(FileHead) + m_slots.size() * sizeof(SlotPtr);
    if (headsize % ncachesize != 0)  // 以ncachesize上对齐
      headsize = (headsize / ncachesize + 1) * ncachesize;

    // MEMSET(buf, 0, nfsize);
    // SlotPtr caches = (SlotPtr)(buf +
    // headsize);//连续CacheLine数组,每个都是256
    int index = 0, keycount = 0;
    std::vector<uint> slots;
    slots.reserve(m_slots.size());  // 连续哈希插槽数组,只有偏移量

    FileHead head;
    memset(&head, 0, sizeof(FileHead));
    head.chunkcount = m_nodecount;
    head.chunkoffset = headsize;
    head.chunksize = sizeof(CacheLine);
    head.hashoffset = sizeof(FileHead);
    head.hashlength = m_slots.size();
    head.keycount = m_count;
    head.magic = Magic;

    fwriter.Append((const char*)&head, sizeof(FileHead));
    fwriter.Append(0, headsize - sizeof(FileHead));  // 填充0
    for (int i = 0; i < (int)m_slots.size(); i++) {
      SlotPtr cache = m_slots[i];
      slots.emplace_back(cache ? (headsize + index * ncachesize) : 0);
      // 严格顺序访问
      while (cache) {
        SlotPtr next = cache->GetNext();
        uint nextoffset = next ? (headsize + (index + 1) * ncachesize) : 0;
        // memcpy(&(caches[index]), cache, sizeof(CacheLine));
        cache->SetNextOffset(nextoffset);
        fwriter.Append((const char*)cache, sizeof(CacheLine));
        cache->SetNext(next);  // 还原

        // caches[index].SetNextOffset(nextoffset);
        keycount += cache->Count();
        cache = next;
        index++;
      }
    }
    // BASSERTS(m_count == keycount, "%d!=%d", m_count, keycount);
    //  写入头部

    int md5size = sizeof(MD5::tMD5);
    int offset = sizeof(uint) + md5size;

    // 写入哈希数组
    fwriter.Write(sizeof(FileHead), (const char*)&slots[0],
                  sizeof(uint) * m_slots.size());
    // memcpy(buf + sizeof(FileHead), &slots[0], sizeof(uint)*m_slots.size());
    // delete[] slots;
    //  结果表明,整体MD5非常消耗资源,只需要计算哈希数组即可
    //  8ms
    // MD5::FromString((const char*)slots, m_slots.size()*sizeof(uint),
    // head->md5, md5size);
    return nfsize;
  }
  bool Equal(const StringIntHashMap& cont) const {
    auto it = begin();
    auto it2 = cont.begin();
    auto e1 = end(), e2 = cont.end();
    if (m_count != cont.m_count) return false;
    int index = 0;
    int n1 = CalcCount();
    int n2 = cont.CalcCount();
    for (; it != e1 && it2 != e2; ++index, ++it, ++it2) {
      if (it.first() != it2.first()) return false;
      if (it.second() != it2.second()) return false;
    }
    if (it != e1 || it2 != e2) return false;
    return true;
  }
  int CalcFileSize() const {
    const int ncachesize = sizeof(CacheLine);
    int fsize = sizeof(FileHead) + m_slots.size() * sizeof(SlotPtr);
    if (fsize % ncachesize != 0) fsize = (fsize / ncachesize + 1) * ncachesize;
    fsize += GetNodeCount() * ncachesize;
    return fsize;
  }
  int CalcSlotLength(int keycapcity, double keyBytes, double expectLoad) const {
    // 根据每个键值的平均长度,和期望负载,计算合适的哈希长度
    double avgChunkKeyCount = sizeof(CacheLine) * 1.0 / (keyBytes + 1 + 1);
    int slotLength = (int)(keycapcity / (expectLoad * avgChunkKeyCount));
    unsigned short bitcount = 0;
    util::GetUpperExp2(slotLength, bitcount);
    return slotLength;
  }

 protected:
  bool ExpandSlots(int slotCount, bool usePool = true) {
    // 假设slotCount是2的n此幂,不做检查
    if (slotCount == m_slots.size()) {
      BLOGINFO("[CACHE]expand failed %d", slotCount);
      return false;
    }
    StringIntHashMap temp(slotCount);
    temp.m_flag = m_flag;
    if (usePool)
      m_flag |= kFlagUsePool;
    else
      m_flag &= ~kFlagUsePool;
    SlotPtr head = nullptr;  // 使用原先哈希表的CacheLine
    for (int i = 0; i < (int)m_slots.size(); i++) {
      SlotPtr next = m_slots[i];
      m_slots[i] = nullptr;
      while (next) {
        SlotPtr cache = next;
        next = next->GetNext();
        cache->SetNext(nullptr);

        // 如果m_usepool开启,那么不需要转移CacheLine内存,此时useCacheList永远为空
        SlotPtr useCacheList = (m_flag & kFlagUsePool) ? nullptr : head;
        for (int i = 0; i < cache->Count(); i++) {
          const EntryType* et = cache->itemAddr(i);
          useCacheList =
              temp.PutWithCache(et->GetKey(), et->GetValue(), useCacheList);
        }
        // 放到空闲单链表中
        cache->SetNext(useCacheList);
        head = cache;
      }
    }

    // 清除head的单链表,如果m_usepool开启,则析构时一次性销毁,而不是一个个销毁
    int nleft = 0;
    if (!(m_flag & kFlagUsePool)) {
      while (head) {
        CacheLine* temp = head;
        head = head->GetNext();
        DelCache(temp);
        nleft++;
      }
    }
    BLOGINFO("[CACHE]expand %d ==> %d  ntotal:%d nleft:%d", m_slots.size(),
             slotCount, m_nodecount, nleft);
    Swap(temp);
    return true;
  }

  double CalcKeyLength() const {
    int keycount = 0;
    int keysize = 0;
    for (int i = 0; i < (int)m_slots.size(); i++) {
      const CacheLine* cache = m_slots[i];
      while (cache) {
        if (cache->Count() > 0) {
          keysize += sizeof(CacheLine) - cache->space();
          keycount += cache->Count();
        }
        cache = cache->GetNext();
      }
    }
    return keycount <= 0 ? 0 : (keysize * 1.0 / keycount);
  }
  double PredictKeyLenth() const {
    // 预估当前的键的长度,只取最多1000个
    int firstPos = 0;
    int slotStep = 3;
    int slotLen = m_slots.size();
    int keycount = 0, keycapcity = 128;
    int bytes = 0;
    const double dft_bytes = 24.0;
    if (m_count <= 0) return dft_bytes;  // 假设平均长度24;
    for (int i = firstPos; i < slotLen; i += slotStep) {
      if (m_slots[i] == nullptr) continue;
      const CacheLine* cache = m_slots[i];

      for (int k = 0; k < cache->Count(); k++) {
        bytes += cache->itemAddr(k)->GetKey().Bytes();
      }
      keycount += cache->Count();
      if (keycount > keycapcity) break;
    }
    if (keycount <= 0) {
      iterator et = end();
      for (auto it = begin(); it != et && keycount < keycapcity; ++it) {
        bytes += it.first().Bytes();
        keycount++;
      }
    }
    return keycount <= 0 ? dft_bytes : (bytes * 1.0 / keycount);
  }
  CacheLine* NewCache(CacheLine* next) {
    if (m_flag & kFlagUsePool)
      return new (m_pool.Alloc()) CacheLine(next);
    else
#if defined(CCORE_MAC)
    {
      SlotPtr p;
      NEW_CACHE(p, CacheLine, next);
      return p;
    }
#else
      return NEW_CACHE(CacheLine, next);
#endif
  }
  void DelCache(CacheLine* cache) {
    if (m_flag & kFlagUsePool)
      m_pool.Free(cache, sizeof(CacheLine));
    else
      DEL_CACHE(CacheLine, cache);
  }
  SlotPtr& GetSlotHead(int index) { return m_slots[index]; }
  void Clear() {
    if (!(m_flag & kFlagUsePool)) {
      for (int i = 0; i < (int)m_slots.size(); i++) {
        CacheLine* cache = m_slots[i];
        while (cache) {
          CacheLine* temp = cache;
          cache = cache->GetNext();
          DelCache(temp);
          m_nodecount--;
        }
      }
    }
    m_slots.clear();
  }
  int GetNodeCount() const {
    int ncount = 0;
    for (int i = 0; i < (int)m_slots.size(); i++) {
      SlotPtr cache = m_slots[i];
      while (cache) {
        ncount++;
        cache = cache->GetNext();
      }
    }
    return ncount;
  }
  static HashPair splitHash(std::size_t hash) {
    uint8_t tag =
        (hash & 0x000000ff);  // | 0x80;	//
                              // 使用低7个bit用于tag,第8个保留用于识别是否为空
    return std::make_pair(hash, tag);
  }

  template <bool largeSize>
  void PrefetchChunk(CacheLine* chunk) const {
    if (largeSize) prefetchAddr((const char*)chunk + (sizeof(CacheLine) >> 1));
  }

  ChunkIndex Find(KeyType const& key, const HashPair& hp) const {
    int slot = GetPos(hp);
    CacheLine* chunk = m_slots[slot];
    const bool large = sizeof(CacheLine) > 64;
    bool sse2 = sse::supports_sse2();
    while (chunk) {
      if (sse2 && large) PrefetchChunk<large>(chunk);
      int index = chunk->find(key, hp);
      if (index >= 0) return ChunkIndex(chunk, index);
      chunk = chunk->GetNext();
    }
    return ChunkIndex{nullptr, -1};
  }

  // 优先使用cacheList单链表来分配CacheLine,如果使用,消耗头部,返回下一个
  // 如果不使用,直接返回下一个,其他情况,与原先的Put相同
  CacheLine* PutWithCache(const KeyType& key, const ValueType& value,
                          CacheLine* cacheList) {
    // 上层已经保证不可能重复,不需要查找
    auto hp = splitHash(key.GetHash());
    int slot = GetPos(hp);
    SlotPtr cache = m_slots[slot];
    if (cache && cache->PutWithSpace(key, hp, value)) {
      m_count++;
      return cacheList;
    }
    if (cacheList) {
      cache = cacheList;
      cacheList = cacheList->GetNext();
      cache->Clear();
      cache->SetNext(m_slots[slot]);
    } else
      cache = NewCache(cache);
    m_slots[slot] = cache;
    cache->PutDirectly(key, hp, value);
    m_nodecount++;
    m_count++;
    return cacheList;
  }

 public:
  int GetPos(const HashPair& hashPair) const {
    // 如果长度是2的n次方,那么计算位置的速度会更快,但是会浪费
    // 更多的内存
    // 如果m_slots.size()刚好是2的m_bitcount次幂,那么优化计算方式
    // return m_bitcount != 0 ? (hashPair.first >> m_bitcount)&m_bitmask:
    //	hashPair.first%m_slots.size();
    return (hashPair.first >> m_bitcount) & m_bitmask;
  }
  int GetBytes() const {
    if (m_flag & kFlagUsePool) {
      return sizeof(*this) + m_pool.GetBytes();
    }
    Stat st;
    GetStat(st);
    return st.bytes;
  }
  void GetStat(Stat& st) const {
    int slot_hole = 0;
    for (int i = 0; i < (int)m_slots.size(); i++) {
      CacheLine* cache = m_slots[i];
      if (cache)
        cache->GetStat(st);
      else
        slot_hole++;
    }
    st.slot_hole = slot_hole;
    st.slot_count = m_slots.size();
    st.bytes += m_slots.size() * sizeof(SlotPtr);
  }
};

// StringIntEntry
typedef FStringChunk<StringIntEntry, StringView, uint, 256> String256Chunk;
typedef StringIntHashMap<StringIntEntry, StringView, uint, String256Chunk>
    StringChunkMap;

void StringChunkMapTest();
}  // namespace base
}  // namespace qb
